package greedy;

import java.util.PriorityQueue;

//将数组和减半的最小操作次数：https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/
//贪心策略：每次挑选最大的元素，将其减半
public class Code2 {
	public int halveArray(int[] nums) {
        double target=0,sum=0;
        int ret=0;
        for(int x:nums){
            sum+=x;
        }
        target=sum/2;
        //建大根堆，使用大根堆进行维护以随时获取最大值
        PriorityQueue<Double> q=new PriorityQueue<>((a,b)-> b.compareTo(a));
        for(int x:nums){
            q.offer((double)x);
        }
        while(target>0){
            ret++;
            double tmp=q.poll();
            target-=tmp/2;
            q.offer(tmp/2);
        }
        return ret;
    }
}
